package com.fang.tree.print;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。 给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，
 * 所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
 */
public class TreePrinter {
	public static int[][] printTree(TreeNode root) {
		// write code here
		if (root == null) {
			return new int[0][0];
		}
		List<List<Integer>> data = new ArrayList<>();
		TreeNode last = root;
		TreeNode nLast = null;

		Queue<TreeNode> queue = new ArrayDeque<>();
		queue.add(root);

		List<Integer> dataRow = new ArrayList<>();
		int maxLen = 0;
		while (!queue.isEmpty()) {
			TreeNode tempTreeNod = queue.poll();
			dataRow.add(tempTreeNod.val);

			TreeNode left = tempTreeNod.left;
			if (left != null) {
				nLast = left;
				queue.add(left);
			}

			TreeNode right = tempTreeNod.right;
			if (right != null) {
				nLast = right;
				queue.add(right);
			}

			if (tempTreeNod == last) {
				last = nLast;
				data.add(dataRow);
				if (dataRow.size() > maxLen) {
					maxLen = dataRow.size();
				}
				dataRow = new ArrayList<>();
			}
		}

		int[][] dest = new int[data.size()][];
		for (int i = 0; i < data.size(); i++) {
			dest[i] = new int[data.get(i).size()];
			for (int j = 0; j < data.get(i).size(); j++) {
				dest[i][j] = data.get(i).get(j);
			}
		}
		return dest;
	}

	public static void printArrays(int[][] tree) {
		for (int i = 0; i < tree.length; i++) {
			for (int j = 0; j < tree[i].length; j++) {
				System.out.print(tree[i][j] + "  ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.left.left = new TreeNode(4);

		root.right = new TreeNode(3);

		root.right.left = new TreeNode(5);
		root.right.left.left = new TreeNode(7);
		root.right.left.right = new TreeNode(8);

		root.right.right = new TreeNode(6);
		root.right.right.left = new TreeNode(9);
		root.right.right.right = new TreeNode(10);

		int[][] dest = TreePrinter.printTree(root);
		TreePrinter.printArrays(dest);
	}

}
